import sun.security.util.Length;

/**
 * @Auther: wangliuyang
 * @Date: 2021/4/17 21:12
 * @Description:    寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 */
public class Solution_4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        if (((length1 + length2) & 1) == 0) {
            return (this.getEleByK(nums1, 0, length1 - 1, nums2, 0, length2 - 1, (length1 + length2) / 2)
                    +
                    this.getEleByK(nums1, 0, length1 - 1, nums2, 0, length2 - 1, (length1 + length2) / 2 + 1)) / 2.0;
        }
        return this.getEleByK(nums1, 0, length1 - 1, nums2, 0, length2 - 1, (length1 + length2) / 2 + 1);
    }

    /**
     * Desc:中位数问题可以转成求第n/2大的数字，取两个数组n/2-1下标处数字比较大小，较小者左侧可以二分舍去，进而使用二分法
     * @return {@link int}
     * @author wangliuyang
     * @date
     */
    public int getEleByK(int[] nums1, int left1, int right1, int[] nums2, int left2, int right2, int k) {
        int length1 = right1 - left1 + 1;
        int length2 = right2 - left2 + 1;
        if (length1 == 0 || length2 == 0) {
            return length2 == 0 ? nums1[left1 + k - 1] : nums2[left2 + k - 1];
        }
        if (k == 1) {
            return nums1[left1] < nums2[left2] ? nums1[left1] : nums2[left2];
        }
        int pivot = k / 2 - 1;
        int pivot1 = pivot + left1 > right1 ? right1 : pivot + left1;
        int pivot2 = pivot + left2 > right2 ? right2 : pivot + left2;
        if (nums1[pivot1] <= nums2[pivot2]) {
            return getEleByK(nums1, pivot1 + 1, right1, nums2, left2, right2, k - (pivot1 - left1 + 1));
        } else {
            return getEleByK(nums1, left1, right1, nums2, pivot2 + 1, right2, k - (pivot2 - left2 + 1));
        }
    }

    public static void main(String[] args) {
        new Solution_4().findMedianSortedArrays(new int[]{3}, new int[]{1, 2, 4});
    }
}
